原题地址：跳跃游戏 II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
动态规划
利用一个数组记录每个位置跳到最后一个位置所需的最小步数。从后往前扫描，求解当前位置的最小步数时，只需要找到它一步能到达的位置中跳到最后的最小步数是多少，然后在此基础上加一就行了。
具体的实现代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
// 动态规划
const jump1 = function(nums) {
// 记录每个位置跳到最后一个位置所需的最小步数
let dp = new Array(nums.length).fill(0);
// 从后往前遍历
for (let i = nums.length - 2; i >= 0; i --) {
// 如果当前位置比后一个位置跳跃的最大长度刚好大1，那两者所需的最小步数是相等的
// 因为这多的一个长度，刚好够跳到它后面的一个位置
// 不过步数最少要是1
if (nums[i] === nums[i + 1] + 1) {
dp[i] = Math.max(dp[i + 1], 1);
continue;
}
let step = Infinity; // 步数初始设为最大值
// 记录当前位置一步能到达的位置中跳到最后所需的最小步数
for (let j = 1; j <= nums[i] && i + j < nums.length; j ++) {
step = Math.min(step, dp[i + j])
}
// 当前位置在最小步数上加1即可
dp[i] = step + 1;
}
// 返回第一个位置的最小步数
return dp[0];
};
测试：
let start = new Date();
const test = jump1;
console.log(test([2,3,1,1,4])); // 2
console.log(new Date().getTime() - start.getTime()); // 6
时间复杂度： 双重遍历，时间复杂度为$O(n^2)$。实际上每个位置向后遍历的长度都不会超过它到尾部的长度，所以总时间不会超过$1+2+\ldots+n=\frac{n(n-1)}{2}$，不过去除系数后，也是$O(n^2)$
空间复杂度： $dp$数组的长度为$n$，空间复杂度为$O(n)$
贪心算法
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法，就是通过局部最优去寻找全局最优，贪心有效的关键就是通过每一步的选择要能得到最终的最优解。本题中，由于每个位置上小于等于最大跳跃步数的位置都是可能选择的，所以只需选择两步能跳到的最大位置，那么其他的选择都将不可能超过该最优解。
具体的实现代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
const jump2 = function(nums) {
let count = 0;
let i = 0;
while (i < nums.length - 1) {
// 当前位置可以直接跳到终点，结束
if (i + nums[i] >= nums.length -1) {
count ++;
break;
}
// 选择两次跳跃能到达最远的位置
let [index, max] = [i + 1, 0];
for (let j = i + 1; j <= i + nums[i]; j ++) {
if (j + nums[j] > max) {
[index, max] = [j, j + nums[j]];
}
}
i = index; // 跳到局部最优解
count ++; // 跳跃次数加1
}
return count;
};
测试：
let start = new Date();
const test = jump2;
console.log(test([2,3,1,1,4])); // 2
console.log(new Date().getTime() - start.getTime()); // 4
时间复杂度： 只需要一次遍历，时间复杂度为$O(n)$
空间复杂度： 原地解决，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 10,2019